|
In algebra, a presentation of a monoid (or semigroup) is a description of a monoid (or semigroup) in terms of a set Σ of generators and a set of relations on the free monoid Σ∗ (or free semigroup Σ+) generated by Σ. The monoid is then presented as the quotient of the free monoid by these relations. This is an analogue of a group presentation in group theory. As a mathematical structure, a monoid presentation is identical to a string rewriting system (also known as semi-Thue system). Every monoid may be presented by a semi-Thue system (possibly over an infinite alphabet).〔Book and Otto, Theorem 7.1.7, p. 149〕 A ''presentation'' should not be confused with a ''representation''. == Construction == The relations are given as a (finite) binary relation ''R'' on Σ∗. To form the quotient monoid, these relations are extended to monoid congruences as follows. First, one takes the symmetric closure ''R'' ∪ ''R''−1 of ''R''. This is then extended to a symmetric relation ''E'' ⊂ Σ∗ × Σ∗ by defining ''x'' ~''E'' ''y'' if and only if ''x'' = ''sut'' and ''y'' = ''svt'' for some strings ''u'', ''v'', ''s'', ''t'' ∈ Σ∗ with (''u'',''v'') ∈ ''R'' ∪ ''R''−1. Finally, one takes the reflexive and transitive closure of ''E'', which is then a monoid congruence. In the typical situation, the relation ''R'' is simply given as a set of equations, so that . Thus, for example, : is the equational presentation for the bicyclic monoid, and : is the plactic monoid of degree 2 (it has infinite order). Elements of this plactic monoid may be written as for integers ''i'', ''j'', ''k'', as the relations show that ''ba'' commutes with both ''a'' and ''b''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Presentation of a monoid」の詳細全文を読む スポンサード リンク
|